#include<iostream>
#include<vector>
#include<string>
using namespace std;

//474.一和零
int findMaxForm(vector<string>& strs, int m, int n){
    int x = strs.size();

    //状态表示 dp[i][j][k]表示从前i个字符串中挑选，数字0不超过m个，数字1不超过n个的所有选法中，最长子集的长度
    vector<vector<vector<int>>> dp(x + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));

    //初始化 初始值设置为0即可

    //填表
    for (int i = 1; i <= x; i++){
        //统计当前字符串中0和1的个数
        string cur = strs[i - 1];
        int a = 0, b = 0;
        for(auto ch : cur){
            if (ch == '0'){
                a++;
            }
            else{
                b++;
            }
        }
        
        for (int j = 0; j <= m; j++){
            for (int k = 0; k <= n; k++){
                //状态转移方程 根据当前字符串选还是不选分情况讨论 两种情况取最大值
                dp[i][j][k] = dp[i - 1][j][k];

                if (j >= a && k >= b){
                    dp[i][j][k] = max(dp[i - 1][j - a][k - b] + 1, dp[i][j][k]);
                }
            }
        }
    }

    //返回值
    return dp[x][m][n];
}
//空间优化
int findMaxForm(vector<string>& strs, int m, int n){
    int x = strs.size();

    //状态表示
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    //初始化 初始值全部设置为0

    //填表
    for (int i = 1; i <= x; i++){
        //统计当前字符串中的数字0和1个数
        string cur = strs[i - 1];
        int a = 0, b = 0;
        for(auto ch : cur){
            if (ch == '0'){
                a++;
            }
            else{
                b++;
            }
        }

        for (int j = m; j >= a; j--){
            for (int k = n; k >= b; k--){
                //状态转移方程
                dp[j][k] = max(dp[j - a][k - b] + 1, dp[j][k]);
            }
        }
    }

    //返回值
    return dp[m][n];
}

//879.盈利计划
const int N = 1000000007;
int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit){
    int x = group.size();

    //状态表示 dp[i][j][k]表示从前i个计划中挑选，员工个数不超过j，盈利不低于k，总的选法个数
    vector<vector<vector<int>>> dp(x + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));

    //初始化 dp[0][j][0]表示从前0个计划中挑选，员工个数不超过j,盈利不低于0，选法个数为1
    for (int j = 0; j <= n; j++){
        dp[0][j][0] = 1;
    }

    //填表
    for (int i = 1; i <= x; i++){
        for (int j = 0; j <= n; j++){
            for (int k = 0; k <= m; k++){
                //状态转移方程 根据当前计划选还是不选分情况讨论
                //不选
                dp[i][j][k] = dp[i - 1][j][k];

                //选 
                if (j >= group[i - 1]){
                    dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
                }

                dp[i][j][k] %= N;
            }
        }
    }

    //返回值
    return dp[x][n][m];
}
//空间优化
int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit){
    int x = group.size();

    //状态表示
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    //初始化
    for (int j = 0; j <= n; j++){
        dp[j][0] = 1;
    }

    //填表
    for (int i = 1; i <= x; i++){
        for (int j = n; j >= group[i - 1]; j--){
            for (int k = m; k >= 0; k--){
                dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
                dp[j][k] %= N;
            }
        }
    }

    //返回值
    return dp[n][m];
}

int main(){


    return 0;
}